package com.cuz.hot100;

public class Q67addBinary {
    public static void main(String[] args) {
        System.out.println(solution6("1101", "1"));
    }

    public static String solution6(String s1, String s2) {
        if (s1 == null || s2 == null) {
            return "0";
        }
        if (s1.length() == 0) {
            return s2;
        }
        if (s2.length() == 0) {
            return s1;
        }
        if (s1.length() < s2.length()) {
            return solution6(s2, s1);
        }
        //s1 长度大于 s2
        int lessCount = 0;
        boolean hasCarry = false;
        StringBuilder res = new StringBuilder();
        while (lessCount < s2.length()) {
            int s2Value = s2.charAt(s2.length() - lessCount - 1) - '0';
            int s1Value = s1.charAt(s1.length() - lessCount - 1) - '0';
            int sum = s2Value + s1Value + (hasCarry ? 1 : 0);
            if (sum >= 2) {
                sum %= 2;
                hasCarry = true;
            } else {
                hasCarry = false;
            }
            res.append(sum);
            lessCount++;
        }
        for (int index = s1.length() - s2.length() - 1; index >= 0; index--) {
            int s1Value = s1.charAt(index) - '0';
            s1Value += hasCarry ? 1 : 0;
            if (s1Value >= 2) {
                s1Value %= 2;
                hasCarry = true;
            } else {
                hasCarry = false;
            }
            res.append(s1Value);
        }
        if (hasCarry) {
            res.append(1);
        }
        return res.reverse().toString();
    }
}
